1. Field of the Invention
The present invention relates to the generation of random numbers. More particularly, the invention relates to random number generation for a computer system on a computer network.
2. Description of the Related Art
A primary function of a computer networking protocol is to provide an efficient and reliable protocol for the transmission of network packets between computer systems on a computer network.
In a networking environment, a collision is an event in which two or more computer systems on the computer network attempt simultaneous packet transmissions. Computer networking protocols can be divided into two general classes with respect to their collision avoidance techniques; collision abstinence protocols and collision reduction protocols. FIG. 1A shows a computer network 100 which includes a plurality of computer systems 111, 112, . . . 119 coupled together by a computer networking medium 190.
In collision abstinence protocols, collisions are effectively prevented by a token-passing scheme or equivalent in which only one computer system has possession of a token at an instance in time. The only computer system permitted to transmit on networking medium 190 at that instance is the owner of the token. One example of a token-passing scheme is a token ring network.
In contrast, collision reduction protocols require computer systems to listen on the networking medium 190 while transmitting a packet and to retransmit the packet whenever a collision is detected, e.g. Ethernet's collision sense multiple access/collision detect (CSMA/CD) protocol. Subsequently, in order to reduce the probability of another collision clue to simultaneous packet retransmissions, every computer system involved in the initial collision is responsible for backing off for a randomly distributed time interval before attempting another retransmission. In the case of the CSMA/CD protocol, the scheduling of retransmissions is determined by a process called "Truncated Binary Exponential Backoff" which provides a random integer "r", in a range suitable for the transmission medium, for determining the back-off time interval before the retransmission.
Integer "r" must satisfy two main criteria in order to minimize packet collisions while ensuring fair access to the computer network. First, random integers ("r") generated over a period of time should be uniformly distributed over a predetermined range of integers. Second, apparatus/methods for generating integer "r" should ensure that there is minimal correlation between the random integers generated for any two computer systems on the same network. Typically, a random number generator is used to select a suitable back-off time period for rescheduling the packet retransmission. Conventional random number generators include a free-running digital counter and an analog noise source coupled to an analog-to-digital converter, both of which have inherent disadvantages.
For example, digital counters of computer systems coupled to the computer network have a tendency to synchronize upon a network-wide reset caused by for example a network-wide power failure. Further, these counters will continue to increment at approximately the same rate and cause multiple collisions as the computer systems back off for similar time periods. In the case of partially analog solutions such as noise generators, analog circuitry is combined with digital circuitry. As such, a single integrated chip solution requires relatively complex hybrid semiconductor processes, e.g., BiCMOS process. In addition, analog-to-digital converters, occupy substantial semiconductor real estate.
Hence there is a need for a reliable random number generator that produce uniformly distributed numbers in a truly random manner, and is both inexpensive and easy to implement.